/*
 * @lc app=leetcode.cn id=3098 lang=golang
 *
 * [3098] 求出所有子序列的能量和
 */
package Solutions

import (
	"slices"
)

// @lc code=start
func sumOfPowers(nums []int, k int) int {
	slices.Sort(nums)
	cache := make([][][]int, len(nums))
	for i := range cache {
		tem := make([][]int, k)
		for j := range tem {
			tem[j] = make([]int, 0, 32)
		}
		cache[i] = tem
	}
	var dfs func(last int, n int) []int
	var ans = 0
	dfs = func(last int, n int) []int {
		if n == 0 {
			return nil
		}
		if len(cache[last][n]) != 0 {
			return cache[last][n]
		}
		for i := last + 1; i < len(nums)-n+1; i++ {
			t := nums[i] - nums[last]
			tt := dfs(i, n-1)
			var ptt []int
			if tt == nil {
				ptt = []int{t}
			} else {
				ptt = make([]int, len(tt))
				copy(ptt, tt)
				for j := range ptt {
					if ptt[j] > t {
						ptt[j] = t
					}
				}
			}

			cache[last][n] = append(cache[last][n], ptt...)
		}

		return cache[last][n]
	}
	for i := 0; i < len(nums)-k+1; i++ {
		p := dfs(i, k-1)
		for _, v := range p {
			ans = (ans + v) % (1000000000 + 7)
		}
	}
	return ans
}

// @lc code=end
